The present invention relates generally to data processing systems and, more particularly, to a preference-based product browser that utilizes a belief network.
Systems currently exist that display an electronic catalog of products to a user so that the user may select one or more products that suit their needs. These systems typically display hundreds or even thousands of products to the user, and each product may have tens or hundreds of features. When a user is attempting to select a product, however, the user is left to aimlessly peruse the catalog with little or no direction. The user is thus confronted with numerous products with numerous features and must evaluate each product before they can select the product that best suits their needs. Many users become frustrated with the overwhelming task of selecting a product from among numerous choices, and consequently, these users do not purchase a product. It is thus desirable to improve such product selection systems.
An exemplary embodiment of the present invention is described below as using a belief network, so to better explain the details of the exemplary embodiment, an overview of belief networks is presented. A belief network is a representation of the probabilistic relationships among distinctions about the world. A distinction in a belief network can take on a set of values and are thus called variables. A belief network is expressed as an acyclic-directed graph where the variables correspond to nodes, and the relationships between the nodes correspond to arcs. FIG. 1 depicts an example belief network 101. The belief network 101 contains three variables, x1, x2, and x3, which are represented by nodes 102, 106, and 110, respectively. Also, the example belief network 101 contains two arcs 104 and 108. Associated with each variable in a belief network is a set of probability distributions. Using conditional probability notation, the set of probability distributions for a variable can be denoted by p(xi|pa(xi)), where xe2x80x9cpxe2x80x9d refers to the probability distribution and where xe2x80x9cpa(xi)xe2x80x9d denotes the parents of variable xi. Thus, this expression reads as follows, xe2x80x9cthe probability distribution for variable xi given the parents of xi.xe2x80x9d For example, x1 is the parent of x2. The probability distributions specify the strength of the relationships between variables. For instance, if x1 has two states (true and false), then associated with x1 is a single probability distribution p(x1) and associated with x2 are two probability distributions p(x2|x1=t) and p(x2|x1=f).
An important aspect of belief networks is the concept of dependence. Sets of variables x and y are said to be conditionally independent, given a set of variables z, if the probability distribution for x given z does not depend on y. That is, if p(x|z,y)=p(x|z), x and y are conditionally independent given z. If z is empty, however, x and y are said to be xe2x80x9cindependentxe2x80x9d as opposed to conditionally independent. If x and y are not conditionally independent given z, then x and y are said to be conditionally dependent given z.
The arcs in a belief network convey dependence between nodes. When a belief network has an arc from a first node to a second node, the probability distribution of the second node depends upon the value of the first node. For example, belief network 101 contains an arc from node 102 to node 106, and therefore, node 106 is said to be dependent on node 102. Just like the presence of arcs in a belief network conveys dependence, the absence of arcs in a belief network conveys conditional independence. For example, node 102 and node 110 are conditionally independent given node 106. That is, the values of nodes 102 and 110 are conditionally independent if the value of node 106 is known, the condition being the observation of node 106. However, two variables indirectly connected through intermediate variables are dependent given lack of knowledge of the values (xe2x80x9cstatesxe2x80x9d) of the intermediate variables. Therefore, if the value for x2 is unknown, x1 and x3 are dependent.
FIG. 2 depicts an example belief network for troubleshooting automobile problems. The belief network of FIG. 2 contains many variables 202-234 relating to whether an automobile will work properly and arcs 236-268. A few examples of the relationships between the variables follow: For the radio 214 to work properly, there must be battery power 212 (arc 246). Battery power 212, in turn, depends upon the battery working properly 208 and a charge 210 (arcs 242 and 244). The battery working properly 208 depends upon the battery age 202 (arc 236). The charge 210 of the battery depends upon the alternator 204 working properly (arc 238) and the fan belt 206 being intact (arc 240).
The automobile troubleshooting belief network also provides a number of examples of conditional independence and conditional dependence. The operation of the lights 216 and battery power 212 are dependent, and the operation of the lights 216 and operation of the radio 214 are conditionally independent given battery power. The concept of conditional dependence and conditional independence can be expressed using conditional probability notation. For example, the operation of the lights 216 is conditionally independent of the radio 214 given battery power 212. Therefore, the probability of the lights 216 working properly given both the battery power 212 and the radio 214 is equal to the probability of the lights working properly given the battery power alone, P(Lights|Battery Power, Radio)=P(Lights|Battery Power). Also, the probability of the lights 216 working properly is conditionally dependent on the radio 214 given the battery 208. Therefore, the probability of the lights 216 working properly given both the radio 214 and the battery 208 is not equal to the probability of the lights given the battery alone: P(Lights|Radio, Battety)xe2x89xa0(Lights|Battery).
There are two conventional approaches for constructing belief networks. Using the first approach (xe2x80x9cthe knowledge-based approachxe2x80x9d), a person known as a knowledge engineer interviews an expert in a given field to obtain the knowledge of the expert about the expert""s field of expertise. The knowledge engineer and expert first determine the distinctions of the world that are important for decision making in the expert""s field of expertise. These distinctions correspond to the variables of the domain of the belief network. The xe2x80x9cdomainxe2x80x9d of a belief network is the set of all variables in the belief network. The knowledge engineer and the expert next determine the dependencies among the variables (the arcs) and the probability distributions that quantify the strengths of the dependencies.
In the second approach (xe2x80x9cthe data-based approachxe2x80x9d), the knowledge engineer and the expert first determine the variables of the domain. Next, data is accumulated for those variables, and an algorithm is applied that creates a belief network from this data. The accumulated data comes from real world instances of the domain. That is, real world instances of decision making in a given field. Conventionally, this second approach exists for domains containing only discrete variables.
A method for generating a belief network that is an improvement over these conventional approaches is described in U.S. Pat. No. 5,704,018, entitled xe2x80x9cGenerating Improved Belief Networksxe2x80x9d assigned to a common assignee, which is hereby incorporated by reference. This improved method uses both expert knowledge and accumulated data to generate a belief network.
After the belief network has been created, the belief network becomes the engine for a decision-support system. The belief network is converted into a computer-readable form, such as a file, and input into a computer system. Then, the computer system uses the belief network to determine the probabilities of variable states given observations, determine the benefits of performing tests, and ultimately recommend or render a decision. Consider an example where a decision-support system uses the belief network of FIG. 2 to troubleshoot automobile problems. If the engine for an automobile did not start, the decision-based system could request an observation of whether there was gas 224, whether the fuel pump 226 was in working order by performing a test, whether the fuel line 228 was obstructed, whether the distributor 230 was working, and whether the spark plugs 232 were working. While the observations and tests are being performed, the belief network assists in determining which variable should be observed next.
An electronic shopping aid is provided that assists a user in selecting a product from an electronic catalog of products based on their preferences for various features of the products. Since the electronic shopping aid helps a user select a product based on the user""s preferences, it is referred to as a preference-based product browser. In using the browser, the user initially inputs an indication of their like or dislike for various features of the products. In addition, the user may optionally input an indication of how strongly they feel about the like or dislike. In addition to or instead of inputting a like or dislike for features of the product, the user may input a like or dislike for one or more of the products, or the user may input a characteristic of themself, such as their age or income. After receiving this information, the browser then utilizes the information to determine a list of products in which the user is most likely interested. As part of this determination, the browser performs collaborative filtering and bases the determination on what other users with similar characteristics (e.g., age, income, and preference for a product) have liked. After creating this list, the browser displays the list and also displays a list of features which the user has not indicated either a like or a dislike for and which the browser has identified as being most relevant to the determination of the products that the user may like. Thus, by specifying a like or dislike for one or more of these features and products, the user helps the browser to more accurately determine the products in which the user will most likely be interested by having the user state a preference for only those features that the browser deems most important to the determination process.
In accordance with a first aspect of the present invention, a method is provided in a computer system having an electronic shopping aid for predicting a desired product of a user from among available products based on a preference of the user for attributes of the available products. The electronic shopping aid receives a belief network containing attribute nodes and preference nodes, where the attribute nodes reflect the attributes of the available products and where the preference nodes reflect the available products. The electronic shopping aid further receives a request to determine an available product having a greatest likelihood of being the desired product by evaluating probability distributions of the preference nodes given a value of at least one of the attribute nodes and indicates the available product having the greatest likelihood of being the desired product to the user.
In accordance with a second aspect of the present invention, an electronic shopping aid is provided for predicting a desired product of a user based on a preference of the user for attributes of the products. The electronic shopping aid includes a belief network, a receive component, a determination component, and an output component. The belief network contains attribute nodes and preference nodes. The attribute nodes reflect attributes of the products, and the preference nodes reflect the products. Each preference node has a weight that is an indication of how much a value of at least one of the attribute nodes influences whether the available product is the desired product of the user given the value of at least one of the attribute nodes. The receive component receives a request to determine an available product having a greatest likelihood of being the desired product. The request contains a value for at least one of the attribute nodes. The determination component determines the available product having the greatest likelihood of being the desired product by evaluating the weights of the preference nodes given the value of the attribute node. The output component indicates the available product having the greatest likelihood of being the desired product.
In accordance with a third aspect of the present invention, a method is provided in a computer system having a collaborative filtering system for predicting a desired preference of a user based on attributes of the user. The collaborative filtering system receives a belief network containing attribute nodes and preference nodes. The attribute nodes reflect the attributes of the user and have a value. The preference nodes reflect available preferences of the user. Each preference node has a probability indicating the likelihood that the available preference is the desired preference of the user given a value for at least one of the attribute nodes. The collaborative filtering system further receives a request to determine an available preference having a greatest likelihood of being the desired preference, where the request contains a value for at least one of the attribute nodes. Additionally, the collaborative filtering system determines the available preference having the greatest likelihood of being the desired preference by evaluating the probabilities of the preference nodes given the value of the at least one of the attribute nodes or preference nodes, indicates the available preference having the greatest likelihood of being the desired preference, determines which of the attribute nodes are unspecified attribute nodes for which a value was not received in the request, determines an expected value of information for each of the unspecified attribute nodes, and displays to the user the unspecified attribute node with the greatest expected value of information. The expected value of information indicates an importance of a value for the unspecified attribute node in determining the desired preference.